DROPS

Document

DOI: 10.4230/LIPIcs.CSL.2015.24

Simple Parsimonious Types and Logarithmic Space

Authors: Damiano Mazza

Published in: LIPIcs, Volume 41, 24th EACSL Annual Conference on Computer Science Logic (CSL 2015)

Abstract

We present a functional characterization of deterministic logspace-computable predicates based on a variant (although not a subsystem) of propositional linear logic, which we call parsimonious logic. The resulting calculus is simply-typed and contains no primitive besides those provided by the underlying logical system, which makes it one of the simplest higher-order languages capturing logspace currently known. Completeness of the calculus uses the descriptive complexity characterization of logspace (we encode first-order logic with deterministic closure), whereas soundness is established by executing terms on a token machine (using the geometry of interaction).

Cite as

Damiano Mazza. Simple Parsimonious Types and Logarithmic Space. In 24th EACSL Annual Conference on Computer Science Logic (CSL 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 41, pp. 24-40, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{mazza:LIPIcs.CSL.2015.24,
  author =	{Mazza, Damiano},
  title =	{{Simple Parsimonious Types and Logarithmic Space}},
  booktitle =	{24th EACSL Annual Conference on Computer Science Logic (CSL 2015)},
  pages =	{24--40},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-90-3},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{41},
  editor =	{Kreutzer, Stephan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2015.24},
  URN =		{urn:nbn:de:0030-drops-54053},
  doi =		{10.4230/LIPIcs.CSL.2015.24},
  annote =	{Keywords: implicit computational complexity, linear logic, geometry of interaction}
}

Search Results

Documents authored by Mazza, Damiano

Simple Parsimonious Types and Logarithmic Space

Abstract

Cite as

Thanks for your feedback!

Could not send message